//238. 除自身以外数组的乘积
//思路：分别记录下i位置左区间元素的乘积与右区间元素的乘积
//最后ans的i位置的值记录为L[i]*R[i]，返回ans即可


#include <vector>
using namespace std;

class Solution1
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> L(n, 0), R(n, 0);
        L[0] = 1, R[n-1] = 1;//nums[0]不存在左区间，nums[n-1]不存在右区间，分别赋值为1
        //分别记录i位置左右区间元素的乘积
        for(int i = 1; i < n; i++)
        {
            L[i] = L[i-1] * nums[i-1];
        }
        for(int i = n-2; i >= 0; i--)
        {
            R[i] = R[i+1] * nums[i+1];
        }

        vector<int> ans(n, 0);
        for(int i = 0; i < n; i++)
        {
            ans[i] = L[i] * R[i];
        }
        return ans;
    }
};

//优化Solution1
//我们直接用ans保存L数组的数据
//R不用数组存储，不断更新即可
//这样就降低了空间复杂度

class Solution2
{
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> ans(n, 0);
        ans[0] = 1;

        //使用ans数组先保存L的数据
        for(int i = 1; i < n; i++)
        {
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        int R = 1;//R不使用数组保存，而是每次更新
        for(int i = n-1; i >= 0; i--)
        {
            ans[i] = ans[i] * R;
            R = R * nums[i];
        }
    }
};